The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
Computing devices, including, without limitation, switches, routers, and other network devices, often temporarily store data in one or more memories or other storage media. For instance, network devices often buffer significant numbers of data units, such as packets, frames, or cells, until certain events occur and/or until resources become available to process the data units. The storage media in which such data is temporarily stored is often logically and/or physically divided into discrete regions or sections referred to as data buffers (or, simply, “buffers”).
In some computing devices, mechanisms referred to as queues are utilized to determine the orders in which this buffered data is processed. For instance, a first-in-first-out (“FIFO”) queue may be implemented, whereby buffered data units are processed in the order by which they are added to the queue. The queue comprises a series of linked nodes, including a tail node, any number of intermediate nodes, and a head node. Each node corresponds to a different buffered unit of data. Each newly buffered data unit is added to the end, or tail, of the queue, immediately following the data unit previously at the tail of the queue. The “head” of the queue generally corresponds to the oldest item in the queue. When it is time to process a next data unit, the data unit at the head of the queue is removed (also referred to as being “popped” or “released”) from the queue for processing, and the immediately following data unit becomes the head of the queue. As a result of this processing, certain actions may be taken that result in the released data unit being finally processed or otherwise disposed of, and thus no longer buffered.
In some computing devices, there may be multiple queues. These multiple queues may be utilized for different groups of data units, such as different types of data units, or data units associated with different entities. Different queues may exist for different processing components, which may process data units from their respective queues in parallel and/or in series relative to the other processing components. In some embodiments, certain data units may, upon being processed by one processing component, be added to a different queue to await processing by a different component, rather than being removed from its buffer.
Some computing devices may be configured to behave differently depending on the size of a queue. For example, a computing device may enter different states based on the queue size. One such state may be, for example, a discard state in a network device, whereby certain network packets or other data units are discarded rather than buffered, until the size of the corresponding queue falls below a certain threshold. Among other purposes, such a state may be necessary when the queue grows too long, so as to prevent associated data buffers from being overrun, or to meet certain performance guarantees. A variety of other states may be tied to the size of a queue, each having different effects on the behavior of the computing device.